package com.klun.project.common.constans.leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

//给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。
// 在「杨辉三角」中，每个数是它左上方和右上方的数的和。
//
// 示例 1:
//输入: numRows = 5
//输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]
//        1
//       1 1
//      1 2 1
//     1 3 3 1
// 示例 2:
//输入: numRows = 1
//输出: [[1]]
// 提示:
// 1 <= numRows <= 30
// Related Topics 数组 动态规划
// 👍 856 👎 0


public class Solution118 {

	public List<List<Integer>> generate(int numRows) {
		List<List<Integer>> res = new ArrayList<List<Integer>>();
		res.add(Arrays.asList(1));
		if (numRows == 1) return res;
		int[] dp = new int[numRows];
		Arrays.fill(dp, 1);
		res.add(Arrays.asList(1, 1));
		for (int i = 2; i < numRows; i++) {
			List<Integer> temp = new ArrayList<Integer>();
			int t = dp[i / 2];
			for (int j = i / 2; j >= 1; j--) {
				dp[j] = dp[j - 1] + t;
				dp[i - j] = dp[j];
				t = dp[j - 1];
			}
			for (int j = 0; j <= i; j++) {
				temp.add(dp[j]);
			}
			res.add(temp);
		}
		return res;
	}

	public static void main(String[] args) {
		Solution118 solution = new Solution118();
		System.out.println(solution.generate(5));
	}

}
